/*
https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/description/
*/

------------------------------------------------------------------


#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    unordered_map<int, vector<int>> AdjList; // 每个数值对应的相邻节点
    unordered_set<int> Used; // 记录已经访问过的节点

    /**
     * 计算二叉树完全被感染所需的时间。
     *
     * @param Root 二叉树的根节点
     * @param Start 起始感染节点的值
     * @return 完全感染所需的时间
     */
    int AmountOfTime(TreeNode* Root, int Start) {
        if (!Root) return 0; // 如果树为空，返回0
        
        // 构建图结构
        BuildGraph(Root);

        queue<int> Q; // 队列用于广度优先搜索（BFS）
        Q.push(Start);
        Used.insert(Start); // 标记起始节点为已访问
        int Cnt = -1; // 初始化计时器

        // 开始广度优先搜索
        while (!Q.empty()) {
            int Size = Q.size();
            for (int I = 0; I < Size; ++I) {
                int Now = Q.front();
                Q.pop();

                // 将当前节点的所有未访问邻居加入队列
                for (auto Neighbor : AdjList[Now]) {
                    if (!Used.count(Neighbor)) { // 如果邻居节点还没有被访问过
                        Q.push(Neighbor);
                        Used.insert(Neighbor); // 标记邻居节点为已访问
                    }
                }
            }
            Cnt++; // 每处理完一层，时间加1
        }

        return Cnt;
    }

    /**
     * 构建图结构，将二叉树转换为无向图表示。
     *
     * @param Node 当前遍历的节点
     */
    void BuildGraph(TreeNode* Node) {
        if (!Node) return; // 如果节点为空，直接返回

        // 如果存在左子节点，则添加双向边
        if (Node->left) {
            AdjList[Node->val].emplace_back(Node->left->val);
            AdjList[Node->left->val].emplace_back(Node->val);
        }

        // 如果存在右子节点，则添加双向边
        if (Node->right) {
            AdjList[Node->val].emplace_back(Node->right->val);
            AdjList[Node->right->val].emplace_back(Node->val);
        }

        // 递归处理左右子树
        BuildGraph(Node->left);
        BuildGraph(Node->right);
    }
};



----------------------------------------------------------------